#include <string>
#include <vector>
#include <unordered_map>

class patternMatch {
public:
	patternMatch(const string &s): pattern(s) {}
	bool patternMatchingBMH(const string &s, vector<int> &answer);
protected:
	void createOffset(unordered_map<char, int> &offset);
private:
	string pattern;
};

bool patternMatch::patternMatchingBMH(const string &s, vector<int> &answer) {
	unordered_map<char, int> offset;
	createOffset(offset);
	int destlen = s.size(), patlen = pattern.size();
	bool matched = false;
	answer.clear();
	for (int i = 0, j = patlen - 1; i <= destlen - patlen; ) {
		unordered_map<char, int>::iterator it;
		if (s[i+j] != pattern[j]) {
			it = offset.find(s[i+patlen-1]);
			i += (it != offset.end() ? it->second : patlen);
			j = patlen - 1;
		}
		else {
			--j;
			if (j < 0) {
				answer.push_back(i);
				matched = true;
				j = patlen - 1;
				it = offset.find(pattern[patlen-1]);
				i += (it != offset.end() ? it->second : patlen);
			}
		}
	}
	return matched;
}
void patternMatch::createOffset(unordered_map<char, int> &offset) {
	int size = pattern.size();
	for (int i = 0; i != size - 1; ++i) {
		unordered_map<char, int>::iterator it = offset.find(pattern[i]);
		if (it != offset.end())
			it->second = size - i - 1;
		else
			offset.insert(make_pair(pattern[i], size - i - 1));
	}
}